package class04;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author zhangchaoliang
 * create 2022
 */
public class MyHeap1 {

    public static class MyMaxHeap{
        private int[] heap;
        private final int limit;
        private int heapSize;

        public MyMaxHeap(int limit){
            heap = new int[limit];
            this.limit=limit;
            heapSize = 0;
        }

        public boolean isEmpty(){
            return heapSize==0;
        }

        public boolean isFull(){
            return heapSize==limit;
        }

        public void push(int value){
            if (heapSize==limit)
                throw new RuntimeException("heap is full!");
            heap[heapSize]=value;
            heapInset(heap,heapSize++);
        }

        public void heapInset(int[] arr,int index){
            while (arr[index]>arr[(index-1)/2]){
                swap(heap,index,(index-1)/2);
                index = (index-1)/2;
            }
        }

        public void swap(int[] heap,int i,int j){
            int tmp = heap[i];
            heap[i]=heap[j];
            heap[j]=tmp;
        }

        public int pop(){
            int ans = heap[0];
            swap(heap,0,--heapSize);
            heapify(heap,0,heapSize);
            return ans;
        }

        public void heapify(int[] arr,int index,int heapSize){
            int left = index*2+1;
            while (left<heapSize){
                int largest = left+1<heapSize&&arr[left+1]>arr[left]?left+1:left;
                largest=arr[index]>arr[largest]?index:largest;
                if (largest==index)
                    break;
                swap(heap,largest,index);
                index=largest;
                left=index*2+1;
            }
        }
    }

    public static class RightMaxHeap{
        private int[] arr;
        private final int limit;
        private int size;

        public RightMaxHeap(int limit){
            arr=new int[limit];
            this.limit=limit;
            size=0;
        }

        public boolean isEmpty(){
            return size==0;
        }

        public boolean isFull(){
            return size==limit;
        }

        public void push(int value){
            if (size==limit)
                throw new RuntimeException("heap is full!");
            arr[size++]=value;
        }

        public int pop(){
            int maxIndex=0;
            for (int i=0;i<size;i++){
                if (arr[i]>arr[maxIndex])
                    maxIndex=i;
            }
            int ans = arr[maxIndex];
            arr[maxIndex]=arr[--size];
            return ans;
        }
    }

    public static void main(String[] args) {
        int value = 1000;
        int limit = 100;
        int testTime = 500000;
        for (int i=0;i<testTime;i++){
            int curLimit = (int)(Math.random()*limit)+1;
            MyMaxHeap my = new MyMaxHeap(curLimit);
            RightMaxHeap test = new RightMaxHeap(curLimit);
            int curOpTimes = (int)(Math.random()*limit);
            for (int j=0;j<curOpTimes;j++){
                if (my.isEmpty()!=test.isEmpty())
                    System.out.println("Oops!");
                if (my.isFull()!=test.isFull())
                    System.out.println("Oops!");
                if (my.isEmpty()){
                    int curValue = (int)(Math.random()*value);
                    my.push(curValue);
                    test.push(curValue);
                }else if (my.isFull()){
                    if (my.pop()!=test.pop())
                        System.out.println("Oops!");
                }else {
                    if (Math.random()<0.5){
                        int curValue = (int)(Math.random()*value);
                        my.push(curValue);
                        test.push(curValue);
                    }else {
                        if (my.pop()!=test.pop())
                            System.out.println("Oops!");
                    }
                }
            }
        }
        System.out.println("finish!");
    }
}
